#include "KDTree.h"

KDTree::KDTree(void){
}

KDTree::~KDTree(void){
}

void KDTree::buildTree(vector<Triangle> *sceneTriangles, BoundingBox sceneBox){
	Vector3 nextNormal = Vector3(1,0,0);
	KDTreeNode* newFront = new KDTreeNode();
	KDTreeNode* newBack  = new KDTreeNode();

	Vector3 boxRange = sceneBox.maxValues - sceneBox.minValues;
	BoundingBox newFrontBox = sceneBox;
	BoundingBox newBackBox  = sceneBox;
	newFrontBox.maxValues.z = sceneBox.maxValues.z-(boxRange.z*0.5);
	newBackBox.minValues.z  = sceneBox.maxValues.z-(boxRange.z*0.5);
	
	root.planeNormal = Vector3(0,0,1);
	root.position = sceneBox.maxValues-(boxRange*0.5);
	root.AABB = sceneBox;

	//Divide triangles in to child boxes.
	bool frontAdded;
	bool backAdded;
	int axis = 2;
	for(int i = 0; i < (int)sceneTriangles->size(); i++){
		frontAdded = backAdded = false;
		for(int j = 0; j < 3; j++){
			if(!frontAdded && sceneTriangles->at(i).verticies.at(j)[axis] >= root.position[axis]){
				newFront->addTriangle(&(sceneTriangles->at(i)));
				frontAdded = true;
			}
			if(!backAdded && sceneTriangles->at(i).verticies.at(j)[axis] <= root.position[axis]){
				newBack->addTriangle(&(sceneTriangles->at(i)));
				backAdded = true;
			}
		}
	}

	newFront->planeNormal = nextNormal;
	newBack->planeNormal  = nextNormal;
	root.frontChild = newFront;
	root.backChild  = newBack;

	buildTree(newFront, newFrontBox, nextNormal, 1);
	buildTree(newBack,  newBackBox,  nextNormal, 1);
}

void KDTree::buildTree(KDTreeNode *curNode, BoundingBox curBox, Vector3 curNormal, int depth){
	curNode->AABB = curBox;
	//If the current node contains more than the number of triangles desired and is not past the max recursive depth, generate another split.
	if(curNode->triangles.size() > TARGET_TRIANGLES && depth < MAX_KD_DEPTH){
		Vector3 nextNormal;
		KDTreeNode* newFront = new KDTreeNode();
		KDTreeNode* newBack  = new KDTreeNode();
		BoundingBox newFrontBox = curBox;
		BoundingBox newBackBox  = curBox;
		Vector3 boxRange = curBox.maxValues - curBox.minValues;

		curNode->position = curBox.maxValues-(boxRange*0.5);
		int axis = -1;
		if(curNormal.x == 1){
			axis = 0;
			nextNormal = Vector3(0,1,0);
			newFrontBox.maxValues.x = curBox.maxValues.x-(boxRange.x*0.5);
			newBackBox.minValues.x  = curBox.maxValues.x-(boxRange.x*0.5);
		}
		else if(curNormal.y == 1){
			axis = 1;
			nextNormal = Vector3(0,0,1);
			newFrontBox.maxValues.y = curBox.maxValues.y-(boxRange.y*0.5);
			newBackBox.minValues.y  = curBox.maxValues.y-(boxRange.y*0.5);
		}
		else if(curNormal.z == 1){
			axis = 2;
			nextNormal = Vector3(1,0,0);
			newFrontBox.maxValues.z = curBox.maxValues.z-(boxRange.z*0.5);
			newBackBox.minValues.z  = curBox.maxValues.z-(boxRange.z*0.5);
		}

		//Divide triangles in to child boxes.
		bool frontAdded;
		bool backAdded;
		for(int i = 0; i < (int)curNode->triangles.size(); i++){
			frontAdded = backAdded = false;
			for(int j = 0; j < 3; j++){
				if(!frontAdded && curNode->triangles.at(i)->verticies.at(j)[axis] >= root.position[axis]){
					newFront->addTriangle(curNode->triangles.at(i));
					frontAdded = true;
				}
				if(!backAdded && curNode->triangles.at(i)->verticies.at(j)[axis] <= root.position[axis]){
					newBack->addTriangle(curNode->triangles.at(i));
					backAdded = true;
				}
			}
		}

		newFront->planeNormal = nextNormal;
		newBack->planeNormal  = nextNormal;
		curNode->frontChild = newFront;
		curNode->backChild  = newBack;

		buildTree(newFront, newFrontBox, nextNormal, depth+1);
		buildTree(newBack,  newBackBox,  nextNormal, depth+1);
	}
	/*//Otherwise, calculate which triangles intersect with the given bounding box
	else{
		for(int i = 0; i < (int)sceneTriangles->size(); i++){
			if(sceneTriangles->at(i).intersects(curBox)){
				curNode->addTriangle(&(sceneTriangles->at(i)));
			}
		}
	}*/
}